2004

Vaidišová thắng danh hiệu thứ hai trong sự nghiệp tại Tashkent, vượt qua Virginie Razzano trong trận chung kết. Ngày 18 tháng 10, cô lọt vào top 100, đứng thứ 74 thế giới và là tay vợt trẻ nhất trong top 100 tay vợt nữ vào thời điểm đó.

Sau đó, Vaidišová vào đến tứ kết của giải tại Tokyo, Nhật Bản. Tại Mỹ Mở rộng, cô thua tại vòng 1 trước đương kim vô địch cũng như tay vợt số 1 thế giới là Justine Henin-Hardenne.

2005–2007

Vào tháng 1, Vaidišová có trận thắng tại một giải grand slam đầu tiên tại Úc Mở rộng, vượt qua Casey Dellacqua, tuy nhiên cô lại thua tại vòng 3 trước hạt giống số 1 Lindsay Davenport.

Tháng 4–2005, cô lọt vào top 50, đứng hạng 47 thế giới. Cô vào tứ kết Family Circle Cup. Tại Pháp Mở rộng năm 2005, cô có trận thắng đầu tiên trước 1 tay vợt trong top 10, trước đương kim vô địch Anastasia Myskina sau đó thua trước Patty Schnyder tại tứ kết. Cô ở top 40 thế giới, đứng hạng 34 vào ngày 18 tháng 4. Tháng 5, cô lọt vào chung kết giải tại Istanbul, thua trước Venus Williams.

Tại Mỹ Mở rộng, Vaidišová có thành tích tốt nhất tại Mỹ Mở rộng là lọt tới vòng 4, lần này cô thua trước Nadia Petrova. Sau đó cô có 2 danh hiệu WTA liên tiếp tại Seoul, (Hàn Quốc), thắng Jelena Janković và tại Tokyo, Nhật Bản, thắng Tatiana Golovin khi tay vợt này bỏ cuộc. Sau đó, cô vào top 20, đứng hạng 18.